|
Interpolation search (sometimes referred to as extrapolation search) is an algorithm for searching for a given key value in an indexed array that has been ordered by the values of the key. It parallels how humans search through a telephone book for a particular name, the key value by which the book's entries are ordered. In each search step it calculates where in the remaining search space the sought item might be, based on the key values at the bounds of the search space and the value of the sought key, usually via a linear interpolation. The key value actually found at this estimated position is then compared to the key value being sought. If it is not equal, then depending on the comparison, the remaining search space is reduced to the part before or after the estimated position. This method will only work if calculations on the size of differences between key values are sensible. By comparison, the binary search always chooses the middle of the remaining search space, discarding one half or the other, again depending on the comparison between the key value found at the estimated position and the key value sought. The remaining search space is reduced to the part before or after the estimated position. The linear search uses equality only as it compares elements one-by-one from the start, ignoring any sorting. On average the interpolation search makes about log(log(''n'')) comparisons (if the elements are uniformly distributed), where ''n'' is the number of elements to be searched. In the worst case (for instance where the numerical values of the keys increase exponentially) it can make up to O(''n'') comparisons. In interpolation-sequential search, interpolation is used to find an item near the one being searched for, then linear search is used to find the exact item. ==Performance== Using big-O notation, the performance of the interpolation algorithm on a data set of size ''N'' is ''O''(''N''); however under the assumption of a uniform distribution of the data on the linear scale used for interpolation, the performance can be shown to be ''O''(log log ''N'').〔Weiss, Mark Allen (2006). ''Data structures and problem solving using Java'', Pearson Addison Wesley〕〔Armenakis, A. C., Garey, L. E., Gupta, R. D., An adaptation of a root finding method to searching ordered disk files, BIT Numerical Mathematics, Volume 25, Number 4 / December, 1985.〕〔Sedgewick, Robert (1990), ''Algorithms in C'', Addison-Wesley〕 However, Dynamic Interpolation Search is possible in ''o''(log log ''n'') time using a novel data structure.〔Andersson, Arne, and Christer Mattsson. ‘Dynamic Interpolation Search in ''o''(log log ''n'') Time’. In Automata, Languages and Programming, edited by Andrzej Lingas, Rolf Karlsson, and Svante Carlsson, 700:15–27. Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 1993. http://dx.doi.org/10.1007/3-540-56939-1_58.〕 Practical performance of interpolation search depends on whether the reduced number of probes is outweighed by the more complicated calculations needed for each probe. It can be useful for locating a record in a large sorted file on disk, where each probe involves a disk seek and is much slower than the interpolation arithmetic. Index structures like B-trees also reduce the number of disk accesses, and are more often used to index on-disk data in part because they can index many types of data and can be updated online. Still, interpolation search may be useful when one is forced to search certain sorted but unindexed on-disk datasets. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Interpolation search」の詳細全文を読む スポンサード リンク
|